package basic.courseLearn12.problem;

import org.junit.Test;

import java.util.LinkedList;

//滑动窗口问题
public class WindowProblem {

    @Test
    public void test(){
        int[] nums = {4,3,5,4,3,3,6,7};
        int count = 3;
        int[] results = solution_violence(nums, count);
        for (int i = 0;  i <= nums.length-count; i++) {
            System.out.print(results[i]+ " ");
        }
        System.out.println();
        results = solution_slide(nums, count);
        for (int i = 0;  i <= nums.length-count; i++) {
            System.out.print(results[i]+ " ");
        }
    }

    /**
     * 滑动窗口问题--暴力解法
     * @param nums 数组
     * @param count 窗口大小
     * @return 窗口最大值数组
     */
    public int[] solution_violence(int[] nums, int count) {
        //1. 定义输出数组
        int[] nexts = new int[nums.length];
        //2. 循环遍历
        for (int i = 0; i <= nums.length-count; i++) {
            // 2.1 定义max
            int max = nums[i];
            for (int j = i+1; j < i+count; j++) {
                if (nums[j] > max) {
                    max = nums[j];
                }
            }
            // 2.2 定义next
            nexts[i] = max;
        }
        //3. 返回结果
        return nexts;
    }

    /**
     * 滑动窗口问题--滑动窗口法
     * @param nums 数组
     * @param count 窗口大小
     * @return 窗口最大值数组
     */
    public int[] solution_slide(int[] nums, int count) {
        //1. 定义双向队列，返回数组，下标
        int[] nexts = new int[nums.length-count+1];
        int index = 0;
        LinkedList<Integer> queue = new LinkedList<>();
        //2. 循环遍历
        for (int i = 0; i < nums.length; i++) {
            //2.1 队空，直接入队
            if (queue.isEmpty()) {
                queue.add(nums[i]);
            }else{  //2.2 队不为空
                //2.2.1 取堆顶
                int top = queue.peek();
                //2.2.2 比堆顶大
                if (nums[i] > top) {
                    //逐次比较，小弹出，大入队
                    while (!queue.isEmpty() && nums[i] > queue.peek()) {
                        queue.poll();
                    }
                    queue.add(nums[i]);
                }else {  //2.2.3 比堆顶小/相等，入队
                    queue.add(nums[i]);
                    //如果超出窗口大小，弹出队首
                    if (queue.size() > count){
                        queue.poll();
                    }
                }
            }
            //2.3 判断条件，更新nests数组
            if (i >= count-1){
                nexts[index] = queue.peek();
                index++;
            }
        }
        return nexts;
    }

}
